package 分类.二叉堆;


import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class 合并K个升序链表 {
    public ListNode mergeKLists(ListNode[] lists) {
     PriorityQueue<ListNode> q=new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
         @Override
         public int compare(ListNode o1, ListNode o2) {
             return o1.val-o2.val;
         }
     });
     ListNode dummy=new ListNode(-1);
     ListNode p=dummy;
     for (ListNode head:lists){
       if(head!=null){
           q.add(head);
       }

     }

     while (!q.isEmpty()){
         ListNode cue=q.poll();
         p.next=cue;
         if(cue.next!=null){
             q.add(cue.next);
         }
         p=p.next;
     }
     return dummy.next;
    }
}
